public class 零钱兑换II {
    
    public static void main(String[] args) {
        

    }

    public static int change(int amount, int[] coins) {
        
        // 创建一个数组 dp 来存储组成每个金额所需的组合数
        int[] dp = new int[amount + 1];
        
        // 初始化 dp[0] 为 1，因为只有一种方法可以组成金额 0，那就是选择 0 个硬币
        dp[0] = 1;
        
        // 遍历每种硬币
        for (int coin : coins) {
            // 对于当前硬币，更新从它的面额到 amount 的所有金额的 dp 值
            for (int j = coin; j <= amount; j++) {
                // 如果使用当前硬币，则 dp[j] 可以通过 dp[j - coin] 累加得到
                dp[j] += dp[j - coin];
            }
        }
        
        // 返回组成目标金额的组合数
        return dp[amount];
    }
}
